package fun.codedesign.jdk.math.reverse;

public class LinkedList<T> {
    private T element;
    private LinkedList<T> next; // 递归定义 ，末尾链表next为null

    public LinkedList(T element, LinkedList<T> next) {
        this.element = element;
        this.next = next;
    }

    /**
     * 链表翻转
     * <p> 将next赋值为null,然后将next.next的赋值为原链表，递归调用
     *
     * <p>静态方法前面要加泛型才能编译通过
     *
     * @param original
     * @return
     */
    public static <T> LinkedList<T> reverse(LinkedList<T> first) {
        if (null == first) {
            throw new NullPointerException("can not reverse a null collection");
        }
        // 返回最后一个节点
        if (null == first.getNext()) {
            return first;
        }
        // 传入节点的下一个节点
        final LinkedList<T> next = first.next;
        // 传入节点的下一个节点设置为null
        first.next = null;
        // 递归返回最后一个节点
        final LinkedList<T> end = reverse(next);
        // 传入节点的下一个节点翻转设置为传入节点
        next.next = first;
        // 返回原来的最后一个节点为初始节点
        return end;
    }

    public T getElement() {
        return element;
    }

    public LinkedList<T> getNext() {
        return next;
    }
}
